// https://leetcode.cn/problems/unique-paths/

// 算法思路总结：
// 1. 使用滚动数组优化空间复杂度
// 2. 一维数组dp记录当前行的路径数
// 3. 状态转移：dp[j] = dp[j] + dp[j-1]
// 4. 时间复杂度：O(m×n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        vector<int> dp(n, 1); 
        
        for (int i = 1 ; i < m ; i++) 
        {
            for (int j = 1 ; j < n ; j++)
            {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

int main()
{
    int m1 = 3, m2 = 3;
    int n1 = 7, n2 = 2;

    Solution sol;

    cout << sol.uniquePaths(m1, n1) << endl;
    cout << sol.uniquePaths(m2, n2) << endl;

    return 0;
}